package com.binarytree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution18 {

    Map<Integer, Integer> map;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return getTree(inorder, postorder, 0, inorder.length, 0, postorder.length);
    }

    public TreeNode getTree(int[] inorder, int[] posrorder, int inBegin, int inEnd, int postBegin, int postEnd) {
        if (inBegin >= inEnd || postBegin >= postEnd) {
            return null;
        }

        TreeNode root = new TreeNode(posrorder[postEnd-1]);
        int rootIndex = map.get(posrorder[postEnd-1]);
        int len = rootIndex - inBegin;
        root.left = getTree(inorder,posrorder,inBegin,rootIndex,postBegin,postBegin+len);
        root.right = getTree(inorder,posrorder,rootIndex+1,inEnd,postBegin+len,postEnd-1);
        return root;
    }
}
